#include <dbg.h>
#include <gtest/gtest.h>

using std::vector;

class Solution {
public:
    static vector<int> searchRange(vector<int>& nums, const int target) {
        if (nums.empty()) {
            return {-1, -1};
        }

        const auto leftIt = std::lower_bound(nums.begin(), nums.end(), target);
        if (leftIt == nums.end() || *leftIt != target) {
            return {-1, -1};
        }

        const auto rightIt = std::upper_bound(nums.begin(), nums.end(), target);

        int start = static_cast<int>(std::distance(nums.begin(), leftIt));
        int end = static_cast<int>(std::distance(nums.begin(), rightIt)) - 1;
        return {start, end};
    }
};

TEST(Solution, searchRange) {
    vector nums{5, 7, 7, 8, 8, 10};
    EXPECT_EQ(Solution::searchRange(nums, 8), (vector<int>{3, 4}));
}

TEST(Solution, searchRange_NotFound) {
    vector nums{5, 7, 7, 8, 8, 10};
    EXPECT_EQ(Solution::searchRange(nums, 6), (vector<int>{-1, -1}));
}

TEST(Solution, searchRange_Empty) {
    vector<int> nums{};
    EXPECT_EQ(Solution::searchRange(nums, 0), (vector<int>{-1, -1}));
}

int main(int argc, char** argv) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}